The present invention relates to the field of signal processing, and more particularly to pattern matching and signal characterization.
A great variety of systems may be characterized by the property that they receive a signal and attempt to match the received signal to one of a series of candidate or template signals. Such signal or pattern matching is common in diverse fields such as telecommunications, wireless telecommunications, radar, machine vision and control, system automation, manufacturing, quality control, acoustics, optics, measurement, filtering, data analysis, and others. Signal types may include 1-dimensional (1-D) signals, 2-D signals, such as images, as well as 3-D and higher dimensional data sets or signals. Signals may also be either analog or digital signals.
The presence of noise or other distortions in the received signal complicates the task of matching or characterizing the received signal. In many systems, the signal matching task may be greatly aided by the use of transforms, such as the well known Fourier Transform. The Fourier Transform may be used to recast the signal data into the frequency domain, which can make certain characteristics or underlying structure more apparent, and thus easier to characterize.
For example, in the field of telecommunications the signal is usually a time-varying voltage or current. Fourier theory teaches that such signals may be represented as a superposition of sinusoidal signals of various frequencies and phase values. The Fourier Transform, in essence, decomposes or separates a signal waveform or function into sinusoids of different frequency, amplitude, and/or phase, which sum to the original waveform, i.e., the Fourier transform identifies or determines the different frequency sinusoids and their respective amplitudes that can be combined to represent the original signal. Understanding this aspect of a signal is important in determining how the signal will behave, e.g., when it passes through filters, amplifiers and communication channels. Fourier analysis provides a means to determine the frequency spectrum of a given signal, i.e., to determine the frequency content of a signal. Even discrete digital communications which use 0""s or 1""s to send information still have frequency content. The Fourier Transform may be used to move the signal data from the time domain to the frequency domain where the spectral content of the signal may be easily analyzed or compared to other transformed signals.
In one signal matching approach, the candidate signals are shifted and noise-perturbed versions of each other. A signal generally comprises a series of values, and thus may be thought of as a vector. For example, the candidate signals may comprise an initial signal or vector, and a sequence of signals or vectors which are each phase shifted some amount from its predecessor. In many applications it is necessary to analyze a received input signal to determine which of the candidate signals or vectors most closely matches the input signal. One example of this process is shown in FIGS. 1A and 1B and described as follows.
FIGS. 1A and Bxe2x80x94Signal Matching (Prior Art)
FIGS. 1A and 1B illustrate a prior art method of determining a xe2x80x9cbest fitxe2x80x9d or xe2x80x9cclosest matchxe2x80x9d between an input signal of interest and a set of N candidate signals f, wherein the candidate signals are shifted versions of each other. When the set of candidate signals are shifted versions of each other, then the signals will exhibit properties whereby Fourier techniques may be used in making the determination. FIG. 1A illustrates a preprocessing technique that may be used to preprocess the set f of candidate signals prior to receipt of the signal of interest. This preprocessing performed in FIG. 1A enables a faster and hence more xe2x80x9creal timexe2x80x9d determination of the closest candidate signal in the set of candidate signals f when the input signal is received as shown in FIG. 1B.
As shown in FIG. 1A, in step 102 the set of candidate signals f may be stored in a memory. As mentioned above, the set of candidate signals f comprises an initial signal f0 and shifted versions of the signal f0, referred to as f1, f2, . . . fN-1. In step 104 the method may include selecting a frequency, e.g., the kth frequency, that is present in each of these candidate signals. Step 104 may also be stated as selecting the kth row of a matrix WN wherein the matrix WN comprises the standard Fourier matrix. In step 106 the preprocessing method calculates the value of the Fourier transform at the kth frequency for a first candidate signal in the set of candidate signals. This may be performed by applying the Fourier transform, e.g. an FFT, on the first candidate signal f0 and using the value produced at the respective kth frequency for the Fourier transform calculation. Alternatively, this computation may be performed by computing the vector product between the kth row of the matrix WN and the first candidate signal according to the equation
Fk=WN(k)*f0,
In step 108 the method computes and stores the values of the Fourier transform at the kth frequency for each of the shifted versions of the first signal f0. The values of the Fourier transform at the kth frequency may be referred to as xcex1(n), or alpha(n). The values of the transformation at the kth generalized frequency for the shifted versions of the first signal may be computed according to the expression:
xcex1(n)=exp(2xcfx80n/N k)xc2x7Fk, where Fk is calculated above in 106.
This expression uses the shift invariant property of the Fourier transform to substantially reduce the number of calculations required, i.e., the fact that in the frequency domain the candidate signals are shifted versions of the first signal f0 allows the Fourier transforms of the remainder of the candidate signals to be computed easily from the Fourier transform of the first candidate signal. Alternately, the values of the transformation at the kth generalized frequency for the remaining set of N candidate signals may be computed by applying the Fourier transform at the kth generalized frequency to each of remaining candidate signals, as was applied to the first candidate signal in 106.
The preprocessing performed in FIG. 1A allows a faster determination when an input signal of interest is received. FIG. 1B illustrates the method performed when an input signal of interest g is received to determine the closest match of the set of candidate signals with the input signal g. As shown, in step 122 the input signal of interest g is received. In step 124 the method calculates the Fourier transform, e.g., using an FFT of g at the kth frequency. The value of the Fourier transform of g at the kth frequency may be referred to as alpha bar. The alpha bar value may also be computed according to the equation
{overscore (xcex1)}=WN(k)*g,
where WN(k) refers to the kth row vector of the matrix WN.
In step 126 the method determines the best match between {overscore (xcex1)} and the xcex1(n) values corresponding to each of the candidate signals. This operates to determine the closest candidate signal to the input signal of interest g. In step 128 this closest candidate signal may then be output as a final result.
As noted, the method described in FIGS. 1A and 1B may be used when the set of candidate signals are shifted versions of each other, wherein this characteristic allows the use of Fourier transform techniques to greatly simplify and speed up the analysis. However, when one or more of the signals in the set of candidate signals are not shifted versions of each other, e.g., are uncorrelated, then the method described in FIGS. 1A and 1B cannot be used. The problem of attempting to match a received input signal of interest with one of a set of candidate or template signals, wherein two or more of the signals comprised in the set of candidate or template signals are uncorrelated with each other, arises in many diverse fields. Further, there are no fast techniques available which can be used to determine a closest match between an input signal of interest and a set of uncorrelated signals.
Thus, there exists a substantial need for a system and method for matching a received signal to one of a set of independent candidate signals.
The present invention comprises various embodiments of a system and method for determining or selecting a best match of a received input signal from a set of candidate signals, wherein two or more of the candidate signals are uncorrelated. In a preferred embodiment, the method may comprise a preprocessing phase and a runtime phase for enhanced performance.
In one embodiment of the preprocessing phase, a unified signal transform may be determined from the set of candidate signals. In one embodiment, the unified signal transform may be operable to convert each of the set of candidate signals to a generalized frequency domain, i.e., the unified signal transform may be operable to convert each of the set of candidate signals into a representation of generalized basis functions, wherein the basis functions represent the algebraic structure of the set of candidate signals. Stated another way, the unified signal transform may be operable to decompose the signal into generalized basis functions, wherein the basis functions represent the algebraic structure of the set of candidate signals. In one aspect, the unified signal transform may be considered a type of xe2x80x9cgeneralized Fourier or Frequency Transformxe2x80x9d that is designed specifically for the set of uncorrelated candidate signals.
In one embodiment, calculating the unified signal transform for the set of candidate signals may include:
forming a matrix B from all of the values of the candidate signals, wherein each of the candidate signals comprises a corresponding column of the matrix B;
defining a matrix {acute over (B)}, wherein the matrix {acute over (B)} comprises a column-wise cyclic shifted matrix B;
defining a matrix A, wherein the matrix A comprises a cyclic shift matrix operator, wherein multiplying matrix A times matrix B performs a column-wise cyclic shift on matrix B, thereby generating matrix {acute over (B)}, wherein AB={acute over (B)}, wherein A={acute over (B)}Bxe2x88x921, wherein Bxe2x88x921 comprises an inverse matrix of matrix B, and wherein AN=an Nxc3x97N identity matrix, I;
performing a Jordan decomposition on A={acute over (B)}Bxe2x88x921, thereby generating a relation A=XBxcex9XBxe2x88x921, wherein XB comprises a matrix of normalized columnar eigenvectors of matrix B, wherein A comprises a diagonal matrix of eigenvalues of matrix B, and wherein XBxe2x88x921 comprises an inverse matrix of matrix XB; and
calculating matrix XBxe2x88x921, wherein the matrix XB xe2x88x921 comprises the unified signal transform. It should be noted that the matrix XBxe2x88x921 may be calculate by any of a variety of methods well known in the art.
After the unified signal transform has been determined, the transform may be applied for one or more generalized frequencies to each of the candidate signals in the set to calculate corresponding generalized frequency component values for each of the candidate signals.
In one embodiment of the runtime phase of the present invention, the input signal of interest may be received. The unified signal transform may then be applied for the one or more generalized frequencies to the input signal of interest to calculate corresponding generalized frequency component values for the input signal of interest.
The best match may then be determined between the one or more generalized frequency component values of the input signal of interest and the one or more generalized frequency component values of each of the candidate signals.
Finally, information indicating a best match candidate signal from the set of candidate signals may be output.
In one embodiment, the set of candidate signals may comprise a number of candidate signals, wherein each of the candidate signals comprises a number of values, and wherein the number of values is equal to the number of candidate signals. In other words, the matrix B formed from the candidate signals may comprise a square matrix. In another embodiment, the matrix B may be regular.
In one embodiment, prior to determining a unified signal transform from the set of candidate signals, the initial set of N candidate signals may be manipulated. For example, in the initial set of candidate signals, at least one of the candidate signals may comprise a set of M values, wherein M is not equal to N. In such cases, the candidate signal data may be xe2x80x9cpaddedxe2x80x9d or extended to provide a square matrix B. For example, in an embodiment where M is less than N, additional Nxe2x88x92M values may be provided for the xe2x80x9cshortxe2x80x9d candidate signal, thereby ensuring that each one of the set of candidate signals comprises N values. In one embodiment, providing additional Nxe2x88x92M values may comprise interpolating or extrapolating two or more of the M values to generate the additional Nxe2x88x92M values. Alternately, where M is less than N, a curve may be fit to the M values for the xe2x80x9cshortxe2x80x9d candidate signal, then sampled to generate N values for the candidate signal, thereby ensuring that each one of the set of candidate signals comprises N values.
In another embodiment, the number of initial candidate signals may be less than the number of values in each candidate signal. In one embodiment, additional candidate signals (of N values each) may be provided to ensure a square matrix B. In one embodiment, the additional candidate signals may be chosen or generated arbitrarily.
In one embodiment, after the best match candidate signal has been determined, the best match candidate signal or image may be processed to determine if the best match candidate is an acceptable match. In another embodiment, the best match candidate signal may be processed to determine characteristics of the received input signal of interest. For example, the determined best match candidate signal may comprise a (substantially) noise-free version of the input signal, and thus may be more suitable for determining characteristics of the input signal.
In one embodiment, all of the candidate signals or template images may be uncorrelated with each other. In one embodiment, the input signal of interest and the candidate signals may be 1-dimensional signals, 2-dimensional signals, 3-dimensional signals, or signals of a dimensionality greater than 3. In various applications of the present invention, the input signal of interest and the candidate signals may comprise one or more of image data, measurement data, acoustic data, seismic data, financial data, stock data, futures data, business data, scientific data, medical data, insurance data, musical data, biometric data, and telecommunications signals. It should be noted that these examples are meant to be illustrative only, and are not intended to limit the domain of application of the method.
Various embodiments of the present method may be applied to image characterization or image pattern matching. In one implementation, the invention may comprise various embodiments of a system and method for determining or selecting a best match of a received input image from a set of candidate images, wherein two or more of the candidate images may be uncorrelated.
In some pattern matching embodiments, the set of candidate images may comprise a set of possible images. For example, in a character recognition embodiment, the set of candidate images may comprise images of the set of possible alphanumeric characters. The set of candidate images may also comprise scaled versions of an image (or a plurality of images) and/or may comprise rotated versions of an image (or a plurality of images).
One embodiment of the method performs pattern matching to locate instances of one or more of a plurality of template images in a target image. Each template image may comprise a plurality of pixels, and the target image may also comprise a plurality of pixels. In the preprocessing step, the method first determines a unified signal transform from the set of template images. The method then applies the unified signal transform for at least one generalized frequency to each of the set of template images to calculate a corresponding at least one generalized frequency component value for each of the set of template images.
In the runtime phase, when the target image is received, the method applies the unified signal transform for the at least one generalized frequency to one or more portions of the target image to calculate a corresponding at least one generalized frequency component value for the target image. The method then determines a best match between the at least one generalized frequency component value of the target image and the at least one generalized frequency component value of each of the template images. The method then outputs information indicating a best match template image from the set of template images.
In another embodiment, conventional or other pattern matching techniques may be initially performed on one or more portions of the target image to locate possible template image locations in the target image. For example, correlation based pattern matching may be used to match portions of each template image to the one or more portions of the target image. Those portions of the target image which correlate most strongly with any of the template images may be selected as possible template image locations. These possible template image locations may then be analyzed according to the present invention (i.e., through the use of the unified signal transform) to determine whether instances of any of the template images may be found in the target image. In one embodiment, the initial pattern matching may also use the unified signal transform to determine the possible template image locations in the target image. For example, the initial pattern matching step may apply the present method at a lower image resolution than the final pattern matching process.
The best match template image, or the portion of the target image where the match was found, may then be analyzed or processed in some way, depending on the application. Alternatively, some decisions may be made based on the result of the pattern matching. For example, a machine vision inspection station may perform one or more actions based on the result of the image pattern matching that was performed.